package q152_maxProduct;

public class Solution_1 {
    /*
    相较于53题求出数组的子序列最大和而言
    这里需要求出子序列最大乘积 多出了一个正负的条件
    同样我们可以使用动态规划的方式来求出本题的答案 需要注意的是
    考虑当前位置如果是一个负数的话，那么我们希望以它前一个位置结尾的某个段的积也是个负数，
    这样就可以负负得正，并且我们希望这个积尽可能「负得更多」，即尽可能小。
    如果当前位置是一个正数的话，我们更希望以它前一个位置结尾的某个段的积也是个正数，
    并且希望它尽可能地大。

    因此 我们多维护一个数组 minF 用来记录当前乘积最小的 如果出现了负数的乘积 那么它也就会保存在该数组中
    在我们到达i位置通过动态规划计算最大值时 就可以利用i - 1位置的minF 乘以 i位置的值
    如果i位置是一个正数 那么它在比较时不会受到minF的影响 而如果是一个负数 那么minF与其就能够计算是否达到了一个更大值
     */
    public int maxProduct(int[] nums) {
        int[] minF = new int[nums.length];
        int[] maxF = new int[nums.length];
        minF[0] = nums[0];
        maxF[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            minF[i] = Math.min(nums[i], Math.min(nums[i] * maxF[i - 1], nums[i] * minF[i - 1]));
            maxF[i] = Math.max(nums[i], Math.max(nums[i] * maxF[i - 1], nums[i] * minF[i - 1]));
        }
        int ans = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            ans = Math.max(ans, maxF[i]);
        }
        return ans;
    }
}
